/*
 * acm1586.c
 *
 *  Created on: 5 Apr 2010
 *      Author: xuxu
 */

#include<stdio.h>


int n,node[1001],net[1001][1001];

/*int prim()
{
	int i,j,k,visited[1001]={0};
	int lowcost[1001],min,ret;
	for(i=1;i<n;i++)
		lowcost[i]=net[0][i];
	visited[0]=1;
	ret=0;
	for(i=1;i<n;i++)
	{
		min=99999;
		k=0;
		for(j=1;j<n;j++)
		{
			if(!visited[j]&&lowcost[j]<min)
			{
				min=lowcost[j];
				k=j;
			}
		}
		visited[k]=1;
		ret+=min;
		for(j=1;j<n;j++)
		{
			if(!visited[j]&&net[k][j]<lowcost[j])
			{
				lowcost[j]=net[k][j];
			}
		}
	}
	return ret;
}*/

int prim()
{
	int min,ret;
	int visit[1001]={0};
	int low[1001]={0};
	int i,j,k;
	for(i=1;i<n;i++)
		low[i]=net[0][i];
	visit[0]=1;
	ret=0;
	for(i=1;i<n;i++)
	{
		min=99999;
		k=0;
		for(j=1;j<n;j++)
		{
			if(!visit[j]&&low[j]<min)
			{
				min=low[j];
				k=j;
			}
		}
		ret+=min;
		visit[k]=1;
		for(j=1;j<n;j++)
		{
			if(!visit[j]&&net[k][j]<low[j])
			{
				low[j]=net[k][j];
			}
		}
	}
	return ret;
}

int main()
{
	int count;
	int i,j;
	scanf("%d",&count);
	while(count--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%d",&node[i]);
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&net[i][j]);
				net[i][j]+=node[i]+node[j];
			}
		}
		printf("%d\n",prim());
	}
	return 0;
}
